package org.example.algorithm.dp;

import java.util.ArrayList;
import java.util.List;

public class NumberOfWaysSolution {

    public static void main(String[] args) {
        NumberOfWaysSolution solution = new NumberOfWaysSolution();
        int res = solution.numberOfWays(10, 2);
        System.out.println(res);
    }

    //简化版
    public int numberOfWays(int n, int x) {
        long[] dp = new long[n+1];
        dp[0] = 1;
        for (int i=1;Math.pow(i,x)<=n;i++) {
            for (int j=n;j>=0;j--) {
                if (Math.pow(i,x) <= j) {
                    dp[j] = dp[j] + dp[(int) (j-Math.pow(i,x))];
                }
            }
        }
        return Math.toIntExact(dp[n] % (1000000000 + 7));
    }

    /**
     * 输入：n = 10, x = 2
     * 输出：1
     * @param n
     * @param x
     * @return
     */
    public int numberOfWays2(int n, int x) {
        List<Integer> list = new ArrayList<>();
        for (int i=1;i<=n;i++) {
            int base = 1;
            for (int j=1;j<=x;j++) {
                base *= i;
            }
            if (base <= n) {
                list.add(base);
            } else {
                break;
            }
        }
        long[] dp = new long[n+1];
        dp[list.get(0)] = 1;
        dp[0] = 1;
        for (int i=1;i<list.size();i++) {
            for (int j=n;j>=0;j--) {
                if (list.get(i) <= j) {
                    dp[j] = dp[j] + dp[j-list.get(i)];
                }
            }
        }
        return Math.toIntExact(dp[n] % (1000000000 + 7));
    }
}
